package DPT_18;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution {
	public List<List<Integer>> fourSum(int[] nums, int target) {
		Arrays.sort(nums);
		List<List<Integer>> res = new LinkedList<List<Integer>>();
		for (int i = 0; i < nums.length - 3; i++) {
			if (i > 0 && nums[i] == nums[i - 1]) {
				continue;
			}
			for (int j = i + 1; j < nums.length - 2; j++) {
				if (j > i+1 && nums[j] == nums[j - 1]) {
					continue;
				}
				int start = j + 1, end = nums.length - 1;
				while (start<end) {
					int sum = nums[i]+nums[j]+nums[start]+nums[end];
					if (sum<target) {
						while (start<end&&nums[start]==nums[++start]);
					}else if (sum>target) {
						while (start<end&&nums[end]==nums[--end]);
					}else {
						LinkedList<Integer> temp = new LinkedList<Integer>();
						temp.add(nums[i]);
						temp.add(nums[j]);
						temp.add(nums[start]);
						temp.add(nums[end]);
						res.add(new LinkedList<Integer>(temp));
						while (start<end&&nums[start]==nums[++start]);
					
						while (start<end&&nums[end]==nums[--end]);
						
					}
				}
			}
		}
		return res;

	}
}
